// https://leetcode.cn/problems/the-masseuse-lcci/

// 题干：一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
//      在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
//      给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

// 示例：输入： [1,2,3,1]
//      输出： 4

// 碎语：简单多状态dp

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int massage(vector<int>& nums)
    {
        // 1.状态表示
        // 选择到i位置的时候，此时的最长预约时长
        // 继续细化，fi表示选择到i位置的时候，nums[i]必选，此时的最长预约时长
        // g[i]表示，选择到i位置的时候，nums[i]不选，此时的最长预约时长

        // 2.状态转移方程
        // 线性dp的时候可以多画图
        // fi = gi-1 + nums[i]
        // gi可以分为两种情况 i-1可以选，即fi-1
        // 假设不选，则相当于gi-1,同时注意选最大值

        // 构建dp表和初始化
        int n = nums.size(); if (n == 1) return 0;
        vector<int> f(n), g(n);
        f[0] = nums[0];

        // 填表顺序为从左到右两个表一起填
        for (int i = 1 ; i < n ; i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,2,3,1};

    cout << sol.massage(nums) << endl;

    return 0;
}